class Solution {
public:
    // 4 5 6 7 0 1 2
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[right]) {
                if (nums[mid] > target) 
                    right = mid - 1;
                else  
                    left = mid + 1;
            }
            else {
                if (nums[mid] > nums[right]) {
                    if (target > nums[mid] || target < nums[left]) 
                        left = mid + 1;
                    else  
                        right = mid - 1;
                }
                else {
                    if (target > nums[right] || target < nums[mid]) 
                        right = mid - 1;
                    else  
                        left = mid + 1;
                }
            }
            cout << "left : " << left << "  right : " << right << endl;
        }
        return -1;
    }
}
